首先想到的是，在插入排序中逆序对的个数就是元素交换的次数。这种特性存在于稳定的排序算法中（归并，冒泡，插入），非稳定的（选择）不适用。
归并中的计算，逆序对的数量由 3 个部分组成：逆序对数量=左半部分的逆序对数量+右半部分的逆序对数量+合并部分的逆序对数量。
令 i 作为左半数组的遍历索引，j 作为右半数组的遍历索引。在合并的任何时刻，一旦发现 a[i] 比 a[j] 大，那么会有 (mid – i + 1) 个逆序对。因为 a[i+1], a[i+2] … a[mid-1] 都比 a[j] 大。
那么最后在 merge 中加入相应的计数即可。